package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LC_542_01Matrix {

    public static void main(String[] args) {

    }

    class Solution {
        class Point {
            int x;
            int y;

            Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }

        public int[][] updateMatrix(int[][] matrix) {
            int rows = matrix.length;
            int cols = matrix[0].length;
            int[][] result = new int[rows][cols];
            Queue<Point> q = new LinkedList<>();
            List<Point> q1 = new ArrayList<>();
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (matrix[i][j] == 0) {
                        q.add(new Point(i, j));
                    } else {
                        q1.add(new Point(i, j));
                        result[i][j] = Integer.MAX_VALUE;
                    }
                }
            }
            Point up = new Point(0, 1);
            Point down = new Point(0, -1);
            Point left = new Point(-1, 0);
            Point right = new Point(1, 0);
            Point[] direct = {up, down, left, right};
            while (!q.isEmpty()) {
                Point p = q.poll();
                int x = p.x;
                int y = p.y;
                for (int i = 0; i < 4; i++) {
                    int nx = x + direct[i].x;
                    int ny = y + direct[i].y;
                    if (nx < rows && ny < cols && nx >= 0 && ny >= 0 && result[nx][ny] > result[x][y] + 1) {
                        result[nx][ny] = result[x][y] + 1;
                        q.add(new Point(nx, ny));
                    }
                }
            }
            return result;
        }

    }
}